package chapter07;

/**
 * Created by Miracle yaochengwei on 2022/6/25 15:23
 */
public class MiGong {
    static class T {


//使用递归回溯的思想来解决老鼠出迷宫


        //老韩解读
//1. findWay 方法就是专门来找出迷宫的路径
//2.  如果找到，就返回 true ,否则返回 false
//3. map 就是二维数组，即表示迷宫
//4. i,j 就是老鼠的位置，初始化的位置为(1,1)
//5.  因为我们是递归的找路，所以我先规定 map 数组的各个值的含义
//	0  表示可以走 1  表示障碍物 2  表示可以走 3  表示走过，但是走不通是死路
//6.  当 map[6][5] =2 就说明找到通class T	{
//
//
////使用递归回溯的思想来解决老鼠出迷宫
//
//
////老韩解读
////1. findWay 方法就是专门来找出迷宫的路径
////2.  如果找到，就返回 true ,否则返回 false
////3. map 就是二维数组，即表示迷宫
////4. i,j 就是老鼠的位置，初始化的位置为(1,1)
////5.  因为我们是递归的找路，所以我先规定 map 数组的各个值的含义
////	0  表示可以走 1  表示障碍物 2  表示可以走 3  表示走过，但是走不通是死路
////6.  当 map[6][5] =2 就说明找到通路,就可以结束，否则就继续找.
////7.  先确定老鼠找路策略 下->右->上->左路,就可以结束，否则就继续找.
//7.  先确定老鼠找路策略 下->右->上-> 左
        public boolean findWay(int[][] map, int i, int j) {
            if (map[6][5] == 2) {//说明已经找到路
                return true;
            } else {

                if (map[i][j] == 0) {//当前这个位置0，说明可以走，还没走
                    //我们假定可以走通
                    map[i][j] = 2;
                    //使用找路的策略，来确定该位置是否真的可以走通
                    //下->右->上-> 左
                    if (findWay(map, i + 1, j)) {//先走下
                        return true;
                    } else if (findWay(map, i, j + 1)) {//向右走
                        return true;
                    } else if (findWay(map, i - 1, j)) {//向上走
                        return true;
                    } else if (findWay(map, i, j - 1)) {//向左走
                        return true;
                    } else {
                        map[i][j] = 3;
                        return false;  //上面都走了，走不通就返回false
                    }
                } else {//map[i][j] = 1,2,3  走不通
                    return false;
                }
            }
        }

        //修改找路策略，看看路径是否有变化
        //下->右->上-→>左==> 上->右->下-→>左
        public boolean findWay2(int[][] map, int i, int j) {
            if (map[6][5] == 2) {//说明已经找到路
                return true;
            } else {

                if (map[i][j] == 0) {//当前这个位置0，说明可以走，还没走
                    //我们假定可以走通
                    map[i][j] = 2;
                    //使用找路的策略，来确定该位置是否真的可以走通
                    //下->右->上-> 左
                    if (findWay2(map, i - 1, j)) {//先走上
                        return true;
                    } else if (findWay2(map, i, j + 1)) {//向右走
                        return true;
                    } else if (findWay2(map, i + 1, j)) {//向下走
                        return true;
                    } else if (findWay2(map, i, j - 1)) {//向左走
                        return true;
                    } else {
                        map[i][j] = 3;
                        return false;  //上面都走了，走不通就返回false
                    }
                } else {//map[i][j] = 1,2,3  走不通
                    return false;
                }
            }
        }

        public static void main(String[] args) {
            // 思路
//1.  先创建迷宫，用二维数组表示 int[][] map = new int[8][7];
//2.  先规定 map  数组的元素值: 0  表示可以走 1 表示障碍物
            int[][] map = new int[8][7];//一行7个，一共8列
//3. 将最上面的一行和最下面的一行，全部设置为 1
            for (int i = 0; i < 7; i++) {
                map[0][i] = 1; //0行就是最上面  i 是列在变化
                map[7][i] = 1;//7是最下面的一行 i 是列在变化
            }
            //4.呼最右面的一列和最左面的一列,全部设置为1
            for (int i = 0; i < 8; i++) {
                map[i][0] = 1;
                map[i][6] = 1;//第7列写6
            }
            map[3][1] = 1;
            map[3][2] = 1;
            map[2][2] = 1;//测试回溯
//        map[2][1] = 1;
//        map[2][2] = 1;
//        map[1][2] = 1;

            //输出当前的地图
            System.out.println("=====当前地图情况======");
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[i].length; j++) {
                    System.out.print(map[i][j] + " ");//输出一行
                }
                System.out.println();
            }
            //使用findWay给老鼠找路
            T t1 = new T();
            //下右 上 左
            t1.findWay(map, 1, 1);//开始的位置
            System.out.println("\n========找路的情况如下=========");
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[i].length; j++) {
                    System.out.print(map[i][j] + " ");//输出一行
                }
                System.out.println();
            }
        }
    }
}
